1. Field of the Invention
The present invention relates to an associative memory in which a plurality of storage data are previously stored and a reference data is then inputted thereto in order to retrieve the storage data corresponding to the inputted reference data.
2. Description of the Related Art
Hitherto, there has been proposed an associative memory or a content addressable memory provided with the retrieval function as described above.
FIG. 1 is a circuit block diagram of the conventional associative memory by way of example.
An associative memory 10 is provided with a large number of memory words 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n, each consisting of a memory cell of 32 bits arranged in the transverse direction of the figure, a word being expressed, for example, with 32 bits. Moreover, the associative memory 10 comprises a reference data register 12 which is adapted to latch a word of reference data and a mask data register 13 arranged to store mask data to mask the reference data for each bit in order to compare a bit pattern of the whole or the predetermined part of the reference data not masked with the mask data stored in the mask data register 13 among the reference data latched in the reference data register 12 with a bit pattern of the part corresponding to above bit pattern among the storage data stored in each memory word 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n to detect match or mismatch therebetween. A match signal of a logic "1" is outputted to the match lines 14.sub.-- 1, 14.sub.-- 2 . . . , 14.sub.-- n for the memory words 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n of which bit pattern is matched among the match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n provided corresponding to respective memory words 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n. Meanwhile, a logic "0" appears on the other match lines 14.sub.-- 1, 14.sub.-- 2 . . . , 14.sub.-- n.
The signals outputted to these match lines 14.sub.-- 1, 14.sub.-- 2, . . . , 14.sub.-- n are stored in each match flag register 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n. Here, assuming that, as an example, the signals "0", "1", "1", "0", . . . "0", "0" are respectively stored in the match flag registers 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n, the signals stored in these match flag registers 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n are inputted to an address encoder 16. Thereby, this address encoder 16 outputs an address signal corresponding to the highest priority match flag register among the match flag registers (here, only two match flag registers 15.sub.-- 2 and 15.sub.-- 3) which stores the signal of a logic "1." Supposing that the priority is higher as the number of suffix of the reference numeral is younger, the memory address associated with the match flag register 15.sub.-- 2 is therefore outputted. An address signal AD outputted from this address encoder 16 is then inputted to a decoder 17, if necessary. The decoder 17 decodes the received address signal AD and outputs an access signal to any associated one (here, a word line 18.sub.-- 2) corresponding to the address signal AD of the word lines 18.sub.-- 1, 18.sub.-- 2, . . . , 18.sub.-- n provided corresponding respectively to the memory words 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- n. As a result, data stored in the memory Word 11.sub.-- 2 associated with the word line 18.sub.-- 2 on which the access signal appears is read out to an output register 19.
FIG. 2 is a detailed circuit diagram illustrating a memory word in the associative memory shown in FIG. 1.
This memory word 11 is composed of 32 memory cells 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- 32 of the same structure. Each memory cell 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- 32 is respectively provided with a first inverter 20.sub.-- 1, 20.sub.-- 2, . . . , 20.sub.-- 32 and a second inverter 21.sub.-- 1, 21.sub.-- 2, . . . , 21.sub.-- 32 with the outputs thereof connected to the inputs thereof and these inverters 20.sub.-- 1, 20.sub.-- 2, . . . , 20.sub.-- 32; 21.sub.-- 1, 21.sub.-- 2, . . . , 21.sub.-- 32 operate to store the one bit of a logic "1" or a logic "0" to each memory cell 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- 32.
In each memory cell 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- 32, outputs of the first inverters 20.sub.-- 1, 20.sub.-- 2, . . . , 20.sub.-- 32 are connected to the bit lines 23.sub.-- 1, 23.sub.-- 2, . . . , 23.sub.-- 32 via the transistors 22.sub.-- 1, 22.sub.-- 2, . . . , 22.sub.-- 32 and the gates of these transistors 22.sub.-- 1, 22.sub.-- 2, . . . , 22.sub.-- 32 are connected to the word line 24. In addition, outputs of the second inverters 21.sub.-- 1, 21.sub.-- 2, . . . , 21.sub.-- 32 are connected to the bit bar lines 26.sub.-- 1, 26.sub.-- 2, . . . , 26.sub.-- 32 via the transistors 25.sub.-- 1, 25.sub.-- 2, . . . , 25.sub.-- 32 and the gates of these transistors 25.sub.-- 1, 25.sub.-- 2, . . . , 25.sub.-- 32 are also connected to the word line 24. Furthermore, two transistors 27.sub.-- 1, 28.sub.-- 1; 27.sub.-- 2,. 28.sub.-- 2; . . . ; 27.sub.-- 32, 28.sub.-- 32 connected in series are respectively arranged in each memory cell 11.sub.-- 1,.11.sub.-- 2, . . . , 11.sub.-- 32 to connect between the bit lines 23.sub.-- 1, 23.sub.-- 2, . . . , 23.sub.-- 32 and the bit bar lines 26.sub.-- 1, 26.sub.-- 2, . . . , 26.sub.-- 32 and the gates of the one transistors 27.sub.-- 1, 27.sub.-- 2, . . . , 27.sub.-- 32 among these two transistors 27.sub.-- 1, 28.sub.-- 1; 27.sub.-- 2, 28.sub.-- 2; . . . ; 27.sub.-- 32, 28.sub.-- 32 are connected to the outputs of the first inverters 20.sub.-- 1, 20.sub.-- 2, . . . , 20.sub.-- 32, while the gates of the other transistors 28.sub.-- 1, 28.sub.-- 2, . . . , 28.sub.-- 32 are connected to the outputs of the second inverters 21.sub.-- 1, 21.sub.-- 2, . . . , 21.sub.-- 32.
On the other hands, the match line 140 is provided with transistors 290.sub.-- 1, 290.sub.-- 2, . . . , 290.sub.-- 32 which are associated one by one with each memory cell 11.sub.-- 1, 11.sub.-- 2, . . . , 11.sub.-- 32. These transistors 290.sub.-- 1, 290.sub.-- 2, . . . , 290.sub.-- 32 are connected in series with each other and each gate of the transistors 290.sub.-- 1, 290.sub.-- 2, . . . , 290.sub.-- 32 is connected to the neutral point of respective couple of the transistors 27.sub.-- 1, 28.sub.-- 1; 27.sub.-- 2, 28.sub.-- 2; . . . ; 27.sub.-- 32, 28.sub.-- 32.
In addition, this match line 140 is also connected with an other transistor 290.sub.-- O in series and the left end in FIG. 2 of this match line 140 is grounded via this transistor 290.sub.-- O. The gate of this transistor 290.sub.-- O is connected to a control line 300. Moreover, the right side in FIG. 2 of this match line 140 is provided with an inverter 310. The match line 140 is also extended to the output side of this inverter 310 and is connected to each match flag register 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- n (refer to FIG. 1). A couple of P type transistors 320, 330 are provided between an input of this inverter 310 and the power supply V.sub.DD and the gate of one P type transistor 320 is connected to the control line 300, while the gate of the other P type transistor 330 to the output of the inverter 310.
The match condition is retrieved as explained hereunder in an associative memory comprising memory words having the structure and the peripheral circuits explained above.
First, a logic "0" appears on the control line 300, making conductive the P type transistor 320 in order to precharge the match line 140. In this case, the transistor 290.sub.-- O is turned to the non-conductive state, certainly disconnecting the match line 140 from the ground line. Thereby, precharge is certainly performed. After the match line 140 is precharged, the retrieval operation is performed.
Here, it is assumed that the information of a logic "1" is stored in the memory cell 11.sub.-- 1. That is, in this case, a logic "1" appears on the output side of the first inverter 20.sub.-- 1, while a logic "0" on the output side of the second inverter 21.sub.-- 1.
Assuming that logic "1" is retrieved for the memory cell 11.sub.-- 1, the bit line 23.sub.-- 1 is set to logic "1", while the bit bar line 26.sub.-- 1 is set to logic "0". The word line 24 is maintained in the state of a logic "0". Moreover, the control line 300 is set to logic "1", making conductive the transistor 290.sub.-- O. In this case, a voltage of logic "1" is impressed to the gate of transistor 27.sub.-- 1 and a signal of logic "1" on the bit line 23.sub.-- 1 is impressed to the gate of transistor 290.sub.-- 1, making conductive the transistor 290.sub.-- 1. Namely, when the bit information stored in the memory cell 11.sub.-- 1 coincides with the bit information in the reference data inputted through the bit line 23.sub.-- 1 and the bit bar line 26.sub.-- 1, the corresponding transistor 290.sub.-- 1 is turned to conductive state.
Also, assuming that information of a logic "0" is stored in the memory cell 11.sub.-- 2, the output side of the first inverter 20.sub.-- 2 is set a logic "0" while the output side of the second inverter 21.sub.-- 2 is set a logic "1".
Here, it is also supposed that the state of a logic "1" is retrieved for the memory cell 11.sub.-- 2. Namely, the bit line 23.sub.-- 2 is set to a logic "1", the bit bar line 26.sub.-- 2 to a logic "0" and the control line 300 to a logic "1". In this case, a signal on the bit bar line 26.sub.-- 2 being set to a logic "0" via the transistor 28.sub.-- 2 is inputted to the gate of the transistor 290.sub.-- 2 and thereby this transistor 290.sub.-- 2 is maintained under the non-conductive state. That is, in the case of mismatch, charges precharged in the match line 14 are not discharged.
For the masked bits, both bit line 23.sub.-- 32 and bit bar line 26.sub.-- 32 are set to a logic "1" as illustrated in the memory cell 11.sub.-- 32. In this case, any one of the transistor 27.sub.-- 32 and transistor 28.sub.-- 32 becomes conductive depending on that the information of a logic "1" or a logic-"0" is stored in the memory cell 11.sub.-- 32. In any case, the transistor 290.sub.-- 32 becomes conductive.
As described, in the memory word shown in FIG. 2, when the bit pattern stored in the memory word coincides with the bit pattern of the reference data inputted through the bit lines 23.sub.-- 1, 23.sub.-- 2, . . . , 23.sub.-- 32 and the bit bar lines 26.sub.-- 1, 26.sub.-- 2, . . . , 26.sub.-- 32 (the masked bits are considered to be matched as explained above), the charge precharged in the match line 140 flows through the transistors 290.sub.-- 32, . . . , 290.sub.-- 2, 290.sub.-- 1, 290.sub.-- O. Thereby the match line 140 is discharged, causing the left side from the inverter 310 shown in FIG. 2 of the match line 140 to be turned to the state of a logic "0". This logic "0" is inverted by the inverter 310 and the match signal of logic "1" is outputted from the inverter 310 and is then inputted to the match flag registers 15.sub.-- 1, 15.sub.-- 2, . . . , 15.sub.-- 32 (refer to FIG. 1).
When the bit pattern stored in the memory word does not coincide with the bit pattern of the reference data inputted through the bit lines 23.sub.-- 1, 23.sub.-- 2, . . . , 23.sub.-- 32 and the bit bar lines 26.sub.-- 1, 26.sub.-- 2, . . . , 26.sub.-- 32, the match line 140 is left in the state of a logic "1" by way of the precharge. This logic "1" is then inverted by the inverter 310 and thereby a mismatch signal of a logic "0" is outputted.
As explained, the memory word illustrated in FIG. 2 is so structured that the match line 140 is precharged prior to the retrieval via the P type transistor 320, and is discharged through the transistors 290.sub.-- O, 290.sub.-- 1, . . . , 290.sub.-- 32 only when match is detected by the retrieval operation. Therefore, in many cases, only a small number of the many match lines are discharged for each retrieval operation and the greater number of the match lines are maintained in a precharged condition. Consequently, only the small number of match lines must be precharged again prior to the next retrieval operation, resulting in reduction of power consumption required for retrieval operation.
A circuit structure illustrated in FIG. 2 is only one example of the prior art and many modifications are known or considered.
If only one associative memory results in shortage of memory capacity in the associative memory structured as explained above, it is thought for making access to establish cascade-connection of a plurality of associative. memories (refer to, for example, Japanese Patent Laid-open No. Sho 59-40396 and Japanese Patent Application No. Hei 5-159724 (not yet laid open). In this case, it is preferable that access to a plurality of cascade-connected associative memories can be realized from external circuits only with input or output of the signal similar to that used for making access to only one associative memory.
The Japanese Patent Laid-open No. Sho 59-40396 and Japanese Patent Application No. Hei 5-159724 listed above have proposed the technology that on the occasion of utilizing a function of this associative memory as an ordinary RAM memory to write data to a memory address by designating such address and to read the data from such memory address, the expansion technique of ordinary RAM memory to use ID numbers for discriminating RAM memories as the upper addresses for each RAM memory can be used in direct and the priority for a plurality of integrated associative memories is established also for a priority encoder and so-on. However, it is a problem how to read the contents of the retrieval result register, provided in each associative memory, to which the retrieval result is inputted. It is not preferable, here, to read the contents of the retrieval result register of a plurality of cascade-connected associative memories by designating the ID number of each associative memory, because it has to be considered from the external circuit that a plurality of associative memories are provided.